package com.baixiaowen.xiaoaointerview.Java编程功底篇.五种手写排序.桶排序;

import com.baixiaowen.xiaoaointerview.Java编程功底篇.五种手写排序.快速排序.QuickSortV1;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * 通用版本
 *
 * @author Baixiaowen
 */
public class BucketSortV2 {

    public List<Integer> sort(List<Integer> A, int k, int max, int min) {
        List<LinkedList<Integer>> buckets = new ArrayList<>();
        List<Integer> list = new ArrayList<>();
        int D = max - min + 1;
        QuickSortV1 quickSort = new QuickSortV1();
        for(int i = 0; i < k; i++) {
            buckets.add(new LinkedList<>());
        }

        // 放入桶中
        for(Integer item : A) {
            int key = (item - min) * k / D;
            buckets.get(key).add(item);
        }

        //从桶中取出值
        for(int i = 0; i < k; i++) {
            list.addAll(quickSort.sort(buckets.get(i)));
        }

        return list;

    }
}
